1. Field of the Invention
This invention relates to the compression of pixel data.
2. Related Art
In picture processing applications, particularly video display applications such as those that use one or more standards defined by the Motion Picture Group (MPEG). The amount of memory space required to display and process picture data can be quite large, and can sometimes exceed the capability of the processing entity, commonly a graphics processor in a computer.
As an example, when utilizing the MPEG 2 standard method of processing motion picture data in the PAL format, the amount of picture data which must be stored per frame can be as much as approximately 2.5 megabytes of raw data. Without compression, this image would require five 256 Kxc3x9716 bit memory chips for display. However, using a compression algorithm, the same 2.5 megabyte image can be stored in 2.0 megabytes or less, requiring only four memory chips instead of five. This reduction in memory requirements translates into real cost savings when considering engineering design time, component costs, and the physical space needed for more memory devices and associated control circuits. Thus, it is desirable to reduce the amount of memory space required for storing and displaying pixel data.
One method that is sometimes used in other picture processing contexts is to compress the picture data, that is to rewrite the data in another format, which requires less memory space. There are two types of compression, lossless and lossy. In lossless compression, the entire amount of information can be recovered from the compressed data; whereas in lossy compression, the process of compression loses some information.
Lossless compression would have the advantage of preserving the original pixel data and allowing that information to be recovered from the compressed data. However, known methods of lossless compression, such as the Liv-Zempel compression algorithm, may record individual pixels in fewer or more bits than in the original pixel data, and thus do not preserve the relative locations of pixels in memory. Thus, it can be difficult to identify the pixel data associated with a particular selected pixel.
Known methods of lossy compression suffer from the drawback that information which is lost is occasionally apparent to a viewer, resulting in a degraded display of the video data on the screen. The visual fidelity of the displayed picture width respect to the original image is then lower than desired.
It would be advantageous to provide a method of compressing pixel data in which the compressed pixel data has a high degree of fidelity with the original pixel data, and in which data associated with each pixel of information in a video display can be quickly and easily located i.e. randomly accessed quickly and with the minimum logic. It would also be advantageous to provide a method of compressing data which upon decompression is scalable and capable of being displayed in multiple environments such as TV, PC, or PDA environments.
The invention provides a method and system for pixel data compression in which sets of adjacent pixels are compressed as a block, in a manner, which is sometimes lossy and sometimes lossless. When lossy, the greatest loss in fidelity between the original and the compressed pixels is almost entirely reserved for circumstances where the loss is masked by the high-frequency components of the video data, resulting in a display which is indistinguishable from the original picture.
This invention is not format restricted, and can be used with other video signal formats such as SECAM, NTSC, etc. Depending on the video format being used, there are generally several pixel values which when used together, make up the pixel represented on the display screen. For a pixel R, there might be three bytes of data, each representing a degree of color, one for red, one for green, and one for blue. When choosing the values to be compared in the extant method, data representing common pixel attributes are compared and compressed together. For instance, in pixels R1 through R4, each represented by pixel values 1 through 3, pixel values R11, R21, R31 and R41 would be compared for similarity. Next, pixel values R12, R22, R32, and R42 might be compared, and so on.
The plurality of pixel values in the block are reformatted using a technique in which a first pixel value is represented as an approximate absolute value, and a set of dependent pixel values are represented as approximate relative differences in value. In cases where the relative differences are small or zero, the compression is completely lossless. In cases where the relative differences are larger, the formatting of the first pixel value is responsive to the degree of lossiness required to encode all of the pixels in the memory space allotted.
In a preferred embodiment, the first pixel value and the corresponding dependent pixel relative differences are compressed to a sufficient degree that the resulting compressed values fit within the available memory space.